除算の切り捨て, 切り上げ, 四捨五入
Abstract
整数型同士の割り算を行う際, 切り捨ては容易にできるが, 切り上げや四捨五入するには一工夫が必要.
Explanation
切り捨て
正整数$ x, yに対して, $ \lfloor x / y \rfloor は x // y で計算できる.
切り上げ
正整数$ x, yに対して, $ \lceil x / y \rceilは (x + y - 1) // y で計算できる.
Lemma
正整数$ x, yに対して,$ \left\lceil \frac{x}{y} \right\rceil = \left\lfloor \frac{x + y - 1}{y} \right\rfloor.
Proof
$ xが$ yの倍数のとき. $ x = kyと書くと,
$ \left\lceil \frac{x}{y} \right\rceil = \left\lceil k \right\rceil = k
である. 一方,
$ \left\lfloor \frac{x + y - 1}{y}\right\rfloor = \left\lfloor k + \frac{y - 1}{y} \right\rfloor = k + \left\lfloor \frac{y - 1}{y} \right\rfloor = k
である.
$ xが$ yの倍数でないとき. $ x = ky + r ~ (0 < r < y)とかけるから,
$ \left\lceil \frac{x}{y} \right\rceil = \left\lceil k + \frac{r}{y} \right\rceil = k + \left\lceil \frac{r}{y} \right\rceil = k + 1
である. 一方,
$ \left\lfloor \frac{x + y - 1}{y}\right\rfloor = \left\lfloor k + 1 + \frac{r - 1}{y} \right\rfloor = k + 1 + \left\lfloor \frac{r - 1}{y} \right\rfloor = k + 1
である. $ \blacksquare
四捨五入
正整数$ x, yに対して, $ x / yを四捨五入した結果$ \mathop{\mathrm{round}}(x/y)は (x + (y // 2)) // y で計算できる.
Lemma
正整数$ x, yに対して, $ \mathop{\mathrm{round}} \left( \frac{x}{y} \right) = \left\lfloor \frac{x + \lfloor y/ 2 \rfloor}{y} \right\rfloor.
Proof
$ x = ky + r ~ (0 \le r < y)と書くと,
$ \left\lfloor \frac{x + \lfloor y/ 2 \rfloor}{y} \right\rfloor = \left\lfloor k + \frac{r + \lfloor y/ 2 \rfloor}{y} \right\rfloor = k + \left\lfloor \frac{r + \lfloor y/ 2 \rfloor}{y} \right\rfloor
である.
$ r < \lceil y / 2 \rceilのとき. $ r/y < 1/2である (右の注意参照) これは$ yの偶奇で場合分けするとわかる から,
$ \mathop{\mathrm{round}} \left( \frac{x}{y} \right) = \mathop{\mathrm{round}} \left( k + \frac{r}{y} \right) = k.
である. 一方,
$ 0 \le r + \lfloor y/ 2 \rfloor < \lceil y / 2 \rceil + \lfloor y/ 2 \rfloor = y
であるから,
$ \left\lfloor \frac{x + \lfloor y/ 2 \rfloor}{y} \right\rfloor = k
である.
$ r \ge \lceil y / 2 \rceilのとき. このとき$ r/y \ge 1/2であるから,
$ \mathop{\mathrm{round}} \left( \frac{x}{y} \right) = \mathop{\mathrm{round}} \left( k + \frac{r}{y} \right) = k + 1.
一方,
$ 1 \le k + \frac{r + \lfloor y/ 2 \rfloor}{y} < 2
となり,
$ \left\lfloor \frac{x + \lfloor y/ 2 \rfloor}{y} \right\rfloor = k + 1
である. $ \blacksquare
Implementation
上で示したものをそのまま書くだけ.
code:python
def div_ceil(x, y): return (x + y - 1) // y
def div_round(x, y): return (x + (y // 2)) // y
Verification
上で証明したとおりなので, 見るからに正しい.
References